package codingforgreat.lchot150;

import java.util.HashMap;

public class Lc076 {
    public String minWindow(String s, String t) {
        if(t.length() > s.length()){
            return "";
        }
        String res = s;
        char[] s1 = s.toCharArray();
        char[] s2 = t.toCharArray();
        int ans = s2.length;
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i = 0;i < s2.length;i++){
            if(!map.containsKey(s2[i])){
                map.put(s2[i],0);
            }
            int count = map.get(s2[i]);
            map.put(s2[i],++count);
        }
        int L = 0;
        int R = 0;
        //滑窗
        String temp = "";
        int minLen = Integer.MAX_VALUE;
        int ansl = -1;
        int ansr = -1;
        while(R < s1.length){
            if(map.containsKey(s1[R])){
                int count = map.get(s1[R]) - 1;
                map.put(s1[R],count);
                if(count >= 0){
                    ans--;
                }
            }
            if(ans == 0){
                while (!map.containsKey(s1[L]) || map.get(s1[L]) < 0) {
                    if(map.containsKey(s1[L])){
                        map.put(s1[L],map.get(s1[L]) + 1);
                    }
                    L++;
                }
                if (minLen > R - L + 1) {
                    minLen = R - L + 1;
                    ansl = L;
                    ansr = R;
                }
                ans++;
                map.put(s1[L],map.get(s1[L]) + 1);
                L++;
            }
            R++;
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(ansl, ansr + 1);
    }
}
